package 回溯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 全排列Ⅱ {
    static class Solution{
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> permute(int[] nums){
            if (nums.length==0) return result;
            boolean[] used = new boolean[nums.length];
            Arrays.fill(used,false);
            Arrays.sort(nums);
            permuteHelper(nums,used);
            return result;
        }

        private void permuteHelper(int[] nums, boolean[] used) {
            if (path.size()==nums.length){
                result.add(new ArrayList<>(path));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                //判断去重
                if (i>0&&nums[i]==nums[i-1]&& !used[i - 1]){
                    continue;
                }
                if (!used[i]){
                    used[i]=true;
                    path.add(nums[i]);
                    permuteHelper(nums,used);
                    path.remove(path.size()-1);
                    used[i]=false;
                }
            }

        }
    }
}
